Recently a plurality of methods for generation of pseudorandom sequences with very good statistical characteristics based on employment of cellular automata have been reported. For example, Non-Patent Document 1 discloses two-dimensional cellular automata for generating high quality random number. Below, typical two-dimensional cellular automata (2D-CA) are explained.
Cellular automata (CA) are dynamical systems in which space and time are discrete. A cellular automaton consists of an array of cells, each of which can be in one of a finite number of possible states, updated synchronously in discrete time steps, according to a local, interaction rule. Here, only Boolean automata in which the cellular state, s, ε{0,1} is considered. The state of a cell at the next time step is determined by the current states of a surrounding neighborhood of cells.
The cellular array (grid) is d-dimensional, where d=1, 2, 3, is used in practice. In this section of the present specification, d=2, i.e., two-dimensional grids is considered.
The rule contained in each cell is essentially a finite state machine rule, usually specified in the form of a rule table (also known as the transition function), with an entry for every possible neighborhood configuration of states. The cellular neighborhood of a cell consists of itself and of the surrounding (adjacent) cells. For one-dimensional CAs, a cell is connected to r local neighbors (cells) on either side, where r is referred to as the radius (thus, each cell has 2r+1 neighbors).
For two-dimensional CA (2D-CA), two types of cellular neighborhoods are usually considered. Those are: five cells, consisting of the cell along with its four immediate non-diagonal neighbors (also known as the von Neumann neighborhood) and nine cells, consisting of the cell along with its eight surrounding neighbor. (also known as the Moore neighborhood).
When considering a finite-size grid, cyclic boundary conditions are frequently applied, resulting in a circular grid for the one-dimensional case and in a toroidal one for the two-dimensional case. Fixed, or null, boundary conditions can also be used, in which the grid is surrounded by an outer layer of cells in a fixed state of zero. This latter case is usually easier to implement in hardware.
Non-uniform, or inhomogeneous, cellular automata function in the same way as uniform ones, the only difference being in the cellular rules that need not be identical for all cells. Nonuniform CAs share the basic attractive properties of uniform ones: simplicity, parallelism, and locality.
A suitable background consideration of 2D-CA is available in Non-Patent Document 2, for example.
[Non-Patent Document 1]
M. Tomassini, M. Sipperand, M. Perrenoud, “On the generation of high-quality random number by two-dimensional cellular automata”, IEEE Trans. Computers, vol. 49, pp. 1146-1151, October 2000
[Non-Patent Document 2]
P. P. Chaudhuri, D. R. Chaudhuri, S. Nandiand, S. Chattopadhyay, “Additive Cellular Automata: Theory and Applications”, New York, IEEE Press, 1997.
[Non-Patent Document 3]
S. Wolfram, “Cryptography with Cellular Automata”, Advances in cryptology—CRYPTO85, Lecture Notes in Computer Science, vol. 218, pp. 429-432, 1985
[Non-Patent Document 4]
K. Cattell, S. Zhang, M. Serraand, J. C. Muzio, “2-by-n hybrid cellular automata with regular configuration: Theory and application”, IEEE Trans. Computers, vol. 48, pp. 285-295, March 1999
[Non-Patent Document 5]
A. Klimov and A. Shamir, “Cryptographic applications of T-functions”, SAC'2003, pre-print 15 pages, August 2003, (to appear in Lecture Notes in Computer Science).
[Non-Patent Document 6]
S.-U. Guan and S. Zhang, “An evolutionary approach to the design of controllable cellular automata: structure for random number generation”, IEEE Trans. Evolutionary Computation, vol. 7, pp. 23-36. February 2003.
[Non-Patent Document 7]
P. D. Hortensius, R. D. Mcleod, W. Pries, D. M. Miller and H. C. Card, “Cellular automata-base pseudorandom number generators for built-in self-test”, IEEE Transactions on Computer-Aided Design, vol. 8, pp. 842-859, August 1989.
[Non-Patent Document 8]
M. Mihaljevic, M. P. C. Fossorier and H. Imai, “Fast correlation attack algorithm with the list decoding and an application”, FSE2001, Lecture Notes in Computer Science, vol. 2355, pp. 196-210, 2002.
[Non-Patent Document 9]
N. T. Courtois and W. Meier, “Algebraic attacks on stream ciphers with linear feedback”, EURO-CRYPT2003, Lecture Notes in Computer Science, vol. 2656, pp. 345-359, 2003.
[Non-Patent Document 10]
M. Mihaljevic and H. Imai, “A family of fast keystream generators based on programmable linear cellular automata over GF(q) and time variant table”, IEICE Transactions on Fundamentals, vol. E82-A, pp. 32-39, January 1999.
[Non-Patent Document 11]
G. Marsaglia, “Diehard” (1998). http:JJstat.fsu.eduJgeoJdiehard.htm.
[Non-Patent Document 12]
A. K. Das, A. Ganguly, A. Dasgupta, S. Bhawmik, and P. PalChaudhuri, “Efficient characterization of cellular automata”, IEE Proc. Pt. E, vol. 137, pp. 81-87, January 1990.
[Non-Patent Document 13]
K. Cattell and J. C. Muzio, “Synthesis of one-dimensional linear hybrid cellular automata”, IEEE Trans. Computer-Aided Design, vol. 15, pp. 325-335, March 1996.
[Non-Patent Document 14]
S. Nandi, B. K. Kar and P. Pal Chaudhuri, “Theory and applications of cellular automata in cryptography”, IEEE Trans. Comput., vol. 43, pp. 1346-1357, December 1994.
[Non-Patent Document 15]
W. Meier and O. Staffelbach, “Analysis of pseudorandom sequences generated by cellular automata”, Advances in Cryptology—EUROCRYPT 91, Lecture Notes in Computer Science, vol. 547, pp. 186-189, 1992.
[Non-Patent Document 16]
C. K. Koc and A. M. Apohan, “Inversion of cellular automata iterations”, IEE Proc. Comput. Digit. Tech., vol.-144, pp. 279-284, 1997.
[Non-Patent Document 17]
M. Mihaljevic, “An improved key stream generator based on the programmable cellular automata”, ICICS'97, Lecture Notes in Computer Science, vol. 1334, pp. 181-191, 1997.
[Non-Patent Document 18]
M. Mihaljevic, “Security examination of a cellular automata based pseudorandom bit generator using an algebraic replica approach”, AAECC12, Lecture Notes in Computer Science, vol. 1255, pp. 250-262, 1997.
[Non-Patent Document 19]
S. R. Blackburn, S. Murphy and K. G. Peterson, “Comments on “Theory and Applications of Cellular Automata in Cryptography””, IEEE Trans. Comput., vol. 46, pp. 637-638, May 1997.
[Non-Patent Document 20]
M. Mihaljevic, “Security examination of a cellular automata based pseudorandom bit generator using an algebraic replica approach”, AAECC12, Lecture Notes in Computer Science, vol. 1255, pp. 250-262, 1997.
[Non-Patent Document 21]
A. J. Menezes, P. C. van Oorschot and S. A. Vanstone, Handbook of Applied Cryptography. Boc. Roton: CRC Press, 1997.